package com.cat.dataStructure;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/maximum-good-subarray-sum/description/
 * @create 2025/8/19 10:04
 * @since JDK17
 */

public class Solution33 {
    static HashMap<Integer, Integer> map = new HashMap<>();
    public long maximumSubarraySum(int[] nums, int k) {
        map.clear();
        long ans = Long.MIN_VALUE;
        int n = nums.length;
        long[] prefix = new long[n + 1];
        for (int i = 0; i < n; i++) {
            prefix[i + 1] = prefix[i] + nums[i];
        }
        for (int i = 0, idx1, idx2; i < n; i++) {
            idx1 = map.getOrDefault(nums[i] - k, -1);
            idx2 = map.getOrDefault(k + nums[i], -1);
            if (idx1 != -1) {
                ans = Math.max(ans, prefix[i + 1] - prefix[idx1]);
            }
            if (idx2 != -1) {
                ans = Math.max(ans, prefix[i + 1] - prefix[idx2]);
            }
            if (!map.containsKey(nums[i])) {
                map.put(nums[i], i);
            } else {    // 已经有了，选个更大的
                idx1 = map.get(nums[i]);
                if (prefix[i] < prefix[idx1]) {
                    map.put(nums[i], i);
                }
            }
        }

        return ans == Long.MIN_VALUE ? 0 : ans;
    }
}
